/**
 * All rights Reserved, Designed By 溪云阁
 * Copyright:    Copyright(C) 2016-2020
 */

package com.algorithm;

import java.util.Arrays;

/**
 * 归并算法
 * @author：溪云阁
 * @date：2020年5月3日
 */

public class MergeAlgorithm {

    /**
     * 两路归并算法，两个排好序的子序列合并为一个子序列
     * @author 溪云阁
     * @param a
     * @param left
     * @param mid
     * @param right void
     */
    public static void merge(int[] a, int left, int mid, int right) {
        // 辅助数组
        final int[] tmp = new int[a.length];
        // p1、p2是检测指针，k是存放指针
        int p1 = left, p2 = mid + 1, k = left;
        while (p1 <= mid && p2 <= right) {
            if (a[p1] <= a[p2])
                tmp[k++] = a[p1++];
            else
                tmp[k++] = a[p2++];
        }
        while (p1 <= mid) {
            // 如果第一个序列未检测完，直接将后面所有元素加到合并的序列中
            tmp[k++] = a[p1++];
        }
        while (p2 <= right) {
            // 同上
            tmp[k++] = a[p2++];
        }
        // 复制回原素组
        for (int i = left; i <= right; i++) {
            a[i] = tmp[i];
        }
    }

    /**
     * 归并排序
     * @author 溪云阁
     * @param a
     * @param start
     * @param end void
     */
    public static void mergeSort(int[] a, int start, int end) {
        // 当子序列中只有一个元素时结束递归
        if (start < end) {
            // 划分子序列
            final int mid = (start + end) / 2;
            // 对左侧子序列进行递归排序
            mergeSort(a, start, mid);
            // 对右侧子序列进行递归排序
            mergeSort(a, mid + 1, end);
            // 合并
            merge(a, start, mid, end);
        }
    }

    public static void main(String[] args) {
        final int[] arr = { 2, 3, 5, 1, 23, 6, 78, 34, 23, 4, 5, 78, 34, 65, 32, 65, 76, 32, 76, 9 };
        System.out.println("排序前的数组：" + Arrays.toString(arr));
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("排序后的数组：" + Arrays.toString(arr));
    }

}
